package leetcode_周赛._2021._202104._20210418;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/18 10:35
 * 雪糕的最大数量
 * 01 背包问题 超时
 * 贪心
 */
public class _5735 {

    public int maxIceCream_perfect(int[] costs, int coins) {
        Arrays.sort(costs);
        int ans = 0;
        for (int cost : costs) {
            if (cost <= coins) {
                ++ans;
                coins -= cost;
            }
        }
        return ans;
    }

    public int maxIceCream(int[] costs, int coins) {
        int[] dp = new int[coins + 1];
        dp[0] = 0;
        for (int i = 0; i < costs.length; i++) {
            for (int j = coins; j >= costs[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + 1);
            }
        }
        return dp[coins];
    }
}
